package microsfot.java;

import java.util.Arrays;

import alogrithm.heap.BigHeap;

/**
 * 从数组中查询最小的K个元素或者最大的K个元素
 * 要求在O(n)的时间范围内完成
 * 
 * 按照查询最大的K个元素分析
 * 思路1:
 * 对数组进行降序排序，然后依次取前K个元素
 * 
 * 思路2：
 * 对数组建立一个大根堆，循环遍历K次输出根的堆并调整堆以保持大根堆结构
 * 时间复杂度为kO(lgn)<O(n)
 * @author Administrator
 * [1,2,3,4,5,6,7,8]
 */
public class FindKElements {
	
	public void findMaxKElements(Integer a[],int k){
		if(k>a.length){
			k=a.length;
		}
		BigHeap<Integer> heap=new BigHeap<Integer>(a);
		
		int i=0;
		while(i<k){
		//	System.out.printf("%4d",heap.pop());
			i++;
		}
		
		heap.sort();
		System.out.println("after heap sort");
		System.out.println(heap);
	}
	
	/**
	 * 根据快速排序思想进行查找，对于数组a0...an
	 * 第一步：随机找到一个X，将数组分割为2部分p0 p1
	 * 如果x<p0则p1-p0为第K大数
	 * 如果x>p1,则返回p1中第K大数
	 * @param a
	 * @param k
	 */
	public void findMaxKElementsByQuickPart(Integer a[],int k){
		findMaxKElementsByQuickPart(a,0,a.length-1,k);
	}
	
	/**
	 * 基于快速排序查找第K大的数
	 * @param a
	 * @param i
	 * @param j
	 * @param k
	 */
	private void findMaxKElementsByQuickPart(Integer[] a, int i, int j, int k) {
			if(k>=a.length){
				return;
			}
			
			int index=partition(a, i, j);
			System.out.printf("k=%d\t After part (poivt=%d,i=%d,j=%d)\t a =%s \n" ,k,index,i,j, Arrays.toString(a));
			if(index==k){
				System.out.println("找到第K大数:"+a[index]);
				return;
			}
			
			else if(index<k){
				findMaxKElementsByQuickPart(a, i,index-1,k-index);
			}else{
				findMaxKElementsByQuickPart(a, index+1, j, k);
			}
	}
	
	public int partion2(Integer a[],int i,int j){
		int mid=(i+j)>>1;
		int x=a[mid];
		while(true){
			if(i>=j){
				break;
			}
			
			while(i<j && a[i]<=x){
				i++;
			}
			
			if(i<j){
				a[mid]=a[i];
				j--;
			}
			
			while(i<j && a[j]>=x){
				j--;
			}
			
			if(i<j){
				a[i]=a[j];
				i++;
			}
		}
		a[j]=x;
		return j;
	}
	/**
	 * 快速排序分区，基于挖坑法
	 * 
	 */
	public int partition(Integer a[],int i,int j){
		int x=a[i];
		while(true){
			if(i>=j){
				break;
			}
			
			while(a[j]>=x && i <j ){
				j--;
			}
			
			if(i<j){
				a[i]=a[j];
				i++;
			}
			
			while(a[i]<=x && i<j ){
				i++;
			}
			
			if(i<j){
				a[j]=a[i];
				j--;
			}
		}
		a[i]=x;
		return i;
	}

	private void swap(Integer[] a, int i, int x) {
		int t=a[i];
		a[i]=a[x];
		a[x]=t;
	}
	
	public void sort(Integer a[],int l,int r){
		if(l<r){
			int i=partition(a, l, r);
			sort(a,l,i-1);
			sort(a,i+1,r);
		}
	}
	
	public void sort2(Integer a[],int l,int r){
		if(l<r){
			int i=partion2(a, l, r);
			sort(a,l,i-1);
			sort(a,i+1,r);
		}
	}

	public static void main(String[] args) {
		Integer a[]=new Integer[]{100,2,3,4,5,6};
		FindKElements find=new FindKElements();
//		find.findMaxKElements(a, 3);
		
		//快排查找第K大数
//		int part=find.partition(a, 0, a.length-1);
//		System.out.println(part);
//		System.out.println(Arrays.toString(a));
//		
		//find.sort2(a, 0, a.length-1);
		System.out.println(Arrays.toString(a));
		System.out.println(a[1]);
//		System.out.println(Arrays.toString(a));
//		
		find.findMaxKElementsByQuickPart(a, 1);
	}
}
